/*
*	字符串
*/



//最长公共前缀
//https://leetcode.cn/problems/longest-common-prefix/description/
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        if (n == 0) return "";
        else if (n == 1) return strs[0];
        int n1 = strs[0].size();
        for(int i = 0;i<n1;++i)
        {
            char tar = strs[0][i]; //取第一个字符串的第一个字符进行比较
            for(int k = 1;k<n;++k)
                if(i == strs[k].size() || tar != strs[k][i]) return strs[0].substr(0,i);
        }
        return strs[0]; //全部比较完了 表示所有都一样
    }
};


//最长回文子串
//https://leetcode.cn/problems/longest-palindromic-substring/submissions/
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();

        //以每一个字母为中心 向外扩展
        int len = 0,begin = 0,end = 0;
        for(int i = 0;i<n;++i)
        {
            //奇数下标 指向同一个位置
            int left=i,right=i;
            while(left>=0 && right<n && s[left]==s[right]) --left,++right;
            if(right-left-1>len)
            {
                len = right-left-1;
                begin=left+1;
                end = right-1;
            }
            //偶数下标 指向两边
            left=i,right=i+1;
            while(left>=0 && right<n && s[left]==s[right]) --left,++right;
            if(right-left-1>len)
            {
                len = right-left-1;
                begin=left+1;
                end = right-1;
            }
        }
        return s.substr(begin,end-begin+1);
    }
};



//二进制求和
//https://leetcode.cn/problems/add-binary/
class Solution {
public:
    string addBinary(string a, string b) {

        int pos1 = a.size()-1, pos2 = b.size()-1;
        int next = 0; //进位标志
        string ret;
        ret.reserve(max(pos1, pos2) + 2);
        while (pos1 >= 0 && pos2 >= 0)
        {
            int num = (a[pos1--] - '0') + (b[pos2--] - '0') + next;
            next = num / 2;
            ret.push_back((num % 2) + '0');
        }
        while (pos1 >= 0)
        {
            int num = (a[pos1--] - '0') + next;
            next = num / 2;
            ret.push_back((num % 2) + '0');
        }
        while (pos2 >= 0)
        {
            int num = (b[pos2--] - '0') + next;
            next = num / 2;
            ret.push_back((num % 2) + '0');
        }
        if(next) ret.push_back('1');
        reverse(ret.begin(), ret.end());
        return ret;
    }
};



//字符串相乘
//https://leetcode.cn/problems/multiply-strings/submissions/
class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1.size()==1 && num1[0]=='0') return "0";
        else if(num2.size()==1 && num2[0]=='0') return "0";

        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        int n1 = num1.size(), n2 = num2.size();
        vector<int> tmp(n1 + n2 - 1);
        for (int i = 0; i < n1; ++i)
            for (int k = 0; k < n2; ++k)
                tmp[i + k] += (num1[i] - '0') * (num2[k] - '0');

        string ret;
        ret.reserve(n1 + n2);
        int next = 0;
        for (int& n : tmp)
        {
            n += next;
            next = n / 10;
            n %= 10;
        }
        if (next) ret.push_back(next + '0');

        for (int i = n1+n2-2; i >= 0; --i)
            ret.push_back(tmp[i] + '0');

        return ret;
    }
};



